第十一章 定时器

网络程序需要处理的第三类事件是定时事件，比如定期检测一个客户连接的活动状态服务器程序通常管理着众多定时事件，因此有效地组织这些定时事件，使之能在预期的时间点被触发且不影响服务器的主要逻辑，对于服务器的性能有着至关重要的影响。为此，我们要将每个定时事件分别封装成定时器，并使用某种容器类数据结构，比如链表、排序链表和时间轮，将所有定时器串联起来，以实现对定时事件的统一管理。本章主要讨论的就是两种高效的管理定时器的容器：时间轮和时间堆。

11.1 socket选项SO_RCVTIMEO 和SO_SNDTIMEO

SO_RCVTIMEO 和SO_SNDTIMEO分别用来设置socket接收和发送数据的超时时间. 因此这两个选项仅对相关系统调用有效, 包括send, sendmsg, recv, recvmsg, accept, connect.

11.2 SIGALRM信号

第十章中提到, 由alarm和setitimer函数设置的实时闹钟一旦超时, 将触发SIGALRM信号, 因此可以通过该信号的信号处理函数来处理定时任务.

(这种计时器是为了和后面要讨论的高效定时器做对比)

基于升序链表的定时器

核心:

• 维护一个超时时间承升序的定时器链表

• 定义一个心搏函数tick, 每隔一段时间就执行一次, 来处理一次链表上到期的任务

  • 从头结点开始依次处理每个定时器, 直到遇到一个尚未到期的定时器.

11.3 IO复用系统调用的超时参数

Linux下的3组IO复用系统调用都带有超时参数(select, poll, epoll), 因此它们也能统一处理定时事件.但是由于IO复用系统调用可能在超时时间到期之前就返回, 所以我们需要不断更新定时参数来反映剩余的时间.

11.4 高性能定时器

时间轮

基于有序链表的定时器存在一个问题, 即添加定时器的效率偏低. 为此, 设计如图所示的时间轮

• (实线)指针指向轮子上的一个槽(slot), 它恒速转动到下一个槽, 每次转动称为一个滴答(tick), 一个滴答的时间称为时间轮的槽间隔si(slot interval), 也就是心搏时间.

• 每个槽指向一条定时器链表, 每条链表上的定时器具有相同的特征: 它们的定时时间相差N*si的整数倍. 时间轮正是利用这个关系将定时器散列到不同的链表中.

• 假如现在指针指向槽cs, 我们要添加一个定时时间为ti的定时器, 则该定时器将被插入槽ts(timer slot)中

  • $ ts = (cs + (ti/si))%N $

• 显然, 要提高定时精度, 就要求si足够小; 要提高执行效率, 则要求N足够大(保证链表尽可能短)

• 还有复杂的时间轮, 可能有多个轮子, 不同的轮子有不同的粒度. 精度高的转一圈, 精度低的可能才往前移动一槽.

• 添加or删除定时器O(1), 执行定时器优于O(n) (slot越多, 效率越高, 轮子多同理)

时间堆

前面讨论的定时方案都是以固定的频率调用心搏函数tck,并在其中依次检测到期的定时器，然后执行到期定时器上的回调函数。设计定时器的另外一种思路是：将所有定时器中超时时间最小的一个定时器的超时值作为心搏间隔。这样，一旦心搏函数tick被调用，超时时间最小的定时器必然到期，我们就可以在tⅵCk函数中处理该定时器。然后，再次从剩余的定时器中找出超时时间最小的一个，并将这段最小时间设置为下一次心搏间隔。如此反复，就实现了较为精确的定时。

最小堆能够高效地找出最小值, 尤其适合这种定时方案.

• 添加定时器时间复杂度为O(logn), 删除复杂度为O(1), 执行效率为O(1)